package com.kclm.se.jcf;

/****
 * 二叉查找树的实现
 * 
 * @author yejf
 * @since JDK8.0
 * @CreateDate 2020年8月14日 下午4:33:04
 * @description 此类用来描述了xxxxx
 *
 */
public class BinarySearchTree<T extends Comparable<T>> {

	/** 树根 */
	private Node<T> root;

	// 其它的属性
	/** 树中节点的数量 */
	private int size;

	/*****
	 * 把数据data 添加到二叉查找树中
	 * 
	 * @param data
	 */
	public void add(T data) {
		// 1. 判断是否是第一个节点，如果是，则直接当做根节点,并返回
		if (this.root == null) {
			this.root = new Node<>(data);
			this.size++;
			//
			return;
		}
		// 2. 找出我们要存放节点所在的父节点
		Node<T> parent = null; // 我们要找的目标节点
		Node<T> cur = this.root; // 当前的节点, 从根开始找
		//
		while (cur != null) {
			// a. 比较
			if (data.compareTo(cur.getData()) > 0) {
				// 往右边去找
				parent = cur;
				cur = cur.getRight(); //
			} else if (data.compareTo(cur.getData()) < 0) {
				// 往左边去找
				parent = cur;
				cur = cur.getLeft();
			} else {
				// 说明我们要添加的元素与已有的元素相同了，根据BST的规则，则此元素添加不进来。
				return;
			}
		} // end of while, 表示 cur 为 null了

		// 3. 在第2步的基础上，决定存放在左边还是右边
		if (data.compareTo(parent.getData()) > 0) {
			// 存放在 parent的右孩子
			parent.setRight(new Node<>(data));
		} else {
			// 存放在 parent的左孩子
			parent.setLeft(new Node<>(data));
		}
		//
		this.size++;
		// .....
	}

	public int size() {
		return this.size;
	}

	/****
	 * 前序遍历 规则是：先 根， 再左孩子，最后右孩子
	 */
	public void preOrder() {
		// 调用以 Node为参数的preOrder
		preOrder(this.root);
	}

	private void preOrder(Node<T> tree) {
		//
		if (tree == null)
			return;
		// 先根
		System.out.print(tree.getData() + " ");
		// 其次，遍历左子树
		preOrder(tree.getLeft());
		// 最后，遍历右子树
		preOrder(tree.getRight());
	}

	/****
	 * 中序遍历 规则是：先 左孩子，再根，最后右孩子
	 */
	public void midOrder() {
		// 调用以 Node为参数的preOrder
		midOrder(this.root);
	}

	private void midOrder(Node<T> tree) {
		//
		if (tree == null)
			return;
		// 先遍历左子树
		midOrder(tree.getLeft());
		// 再根
		System.out.print(tree.getData() + " ");
		// 最后，遍历右子树
		midOrder(tree.getRight());
	}

	/****************
	 * 从BST中删除指定的元素element, 删除后要保证还是一颗"BST"，所以，我们可以分成如下4种情况：
	 * 1.BST中只有一个根节点，并且此根节点就是我们要找的元素 
	 * 2.被删除元素在BST中是叶子节点
	 * 3.被删除元素在BST中不是叶子节点，但是只有一个子节点，这个子节点可以是左孩子或是右孩子 
	 * 4.被删除元素在BST中不是叶子节点，而且拥有左右子孩子。
	 * 这种情况比较复杂，采用如下算法 
	 * 		4.1 从目标节点的右孩子中找出最小的节点
	 * 		4.2 保存此节点后，删除此节点 
	 * 		4.3 把上面保存的最小节点的值赋值给目标节点
	 * 
	 * 为了实现以上的算法，我们需要提供如下辅助方法 
	 * 1. public Node<T> findTargetNode(T val); //此方法用来找到目标节点【也就是要删除的节点】 
	 * 2. public Node<T> findParentNode(T target); //此方法用来找到目标节点的父节点，有可能会是null【删除的是根节点时】 
	 * 3. public Node<T> findMinNodeFromRight(Node<T> target); //从目标节点的右孩子中，找出最小的节点【也就是最底层的左叶子节点】。
	 * 
	 * @param element
	 */
	public void remove(T element) {
		//要查询目标元素
		Node<T> target = findTargetNode(element);
		//如果没有找到目标元素，则直接返回
		if(target == null) {
			return ;
		}
		//1.如果只有一个节点，并且这个节点就是被删除 的元素，则直接删除
		if(this.size == 1 && this.root.getData().compareTo(element) == 0) {
			this.root = null;
			this.size = 0;
			return ;
		}
		//2. 获取目标元素的父元素
		Node<T> parent = findParentNode(element);
		//如果是叶子节点的话
		if(target.getLeft() == null && target.getRight() == null) {
			//如果是父节点的左孩子，则把 parent.left置为null
			if(parent.getLeft().equals(target)) {
				parent.setLeft(null);
			}
			//如果是父节点的右孩子，则把 parent.right置为null
			if(parent.getRight().equals(target)) {
				parent.setRight(null);
			}
		} else
		//3. 被删除元素在BST中不是叶子节点，但是只有一个子节点，这个子节点可以是左孩子或是右孩子 
		if(target.getLeft() != null && target.getRight() == null) {
			//目标节点有左孩子，没有右孩子
			System.out.println("--删除只有左孩子，没有右孩子的节点："+target);
			//
			if(parent.getLeft().equals(target)) {
				parent.setLeft(target.getLeft());
			}
			//如果是父节点的右孩子，则把 parent.right置为null
			if(parent.getRight().equals(target)) {
				parent.setRight(target.getLeft());
			}
		} else
		if(target.getLeft() == null && target.getRight() != null) {
			//目标节点有右孩子，没有左孩子
			System.out.println("--删除只有右孩子，没有左孩子的节点："+target);
			//进一步判断target是parent的左还是右
			if(parent.getLeft().equals(target)) {
				parent.setLeft(target.getRight());
			}
			//如果是父节点的右孩子，则把 parent.right置为null
			if(parent.getRight().equals(target)) {
				parent.setRight(target.getRight());
			}
		} else
		//4. 被删除元素在BST中不是叶子节点，而且拥有左右子孩子。
		if(target.getLeft() != null && target.getRight() != null) {
			//4.1 找到目标节点中的右子树中的最小节点
			Node<T> minNode = findMinNodeFromRight(target);
			//4.2 保存此节点
			T storeNode = minNode.getData();
			//4.3 删除此节点
			remove(minNode.getData());
			//4.4 把storeNode赋值给target
			target.setData(storeNode);
		}
		//节点数减1
		this.size--;
	}

	/******
	 * 从BST中，查询目标元素所在的节点,如果找不到，则返回null
	 * 
	 * @param val
	 * @return
	 */
	public Node<T> findTargetNode(T val) {
		// 1.判断当前的BST是否为 null
		if (this.root == null) {
			return null;
		}
		// 2.依次查询
		return findTargetNode(this.root, val);
	}

	private Node<T> findTargetNode(Node<T> node, T val) {
		if (node == null) {
			System.out.println("\t没有找到 -> " + val);
			return null;
		}
		// 如果目标元素比node节点的值小，则往左边找
		if (node.getData().compareTo(val) > 0) {
			//System.out.println("<<往左孩子树找: " + node.getData() + " -> " + val);
			return findTargetNode(node.getLeft(), val);
		} else if (node.getData().compareTo(val) < 0) {
			//System.out.println(">>往右孩子树找: " + node.getData() + " -> " + val);
			return findTargetNode(node.getRight(), val);
		} else {
			//System.out.println("找到了: " + node);
			return node;
		}
	}

	/**********************
	 * 查询目标节点的父节点
	 * 此方法我采用了循环来实现
	 * @param target
	 * @return
	 */
	public Node<T> findParentNode(T target) {
		// 1.判断当前的BST是否为 null
		if (this.root == null || target == null) {
			return null;
		}
		// 2.其它情况
		Node<T> parent = null;
		Node<T> current = this.root;
		//只要当前节点的值不是我们的目标值，则循环
		while(current.getData().compareTo(target) != 0) {
			//把当前节点赋值给parent
			parent = current; 
			//进一步判断
			if(current.getData().compareTo(target) > 0) {
				//向左边走
				current = current.getLeft();
			} else {
				//向右边走
				current = current.getRight();
			}
		}
		//
		return parent;
	}

	/****************
	 * 从当前节点开始，找出此“树”中最小的节点【也就是最底层的左叶子节点，也有可能是“根”】。
	 * @param current 【这个参数就是调用者传进来的目标节点的“右子树”节点】
	 * @return
	 */
	public Node<T> findMinNodeFromTree(Node<T> right) {
		//存在左孩子，就往左,直到最后的叶子节点
		if(right.getLeft() != null) {
			//
			return findMinNodeFromTree(right.getLeft());
		} else {
			//不存在左孩子，就返回当前根
			return right;
		}
		
	}

	/*****
	 * 此方法的功能同 findMinNodeFromTree, 这里采用了 循环来实现，没有使用递归
	 * @param target 目标节点【不是目标节点的右节点】
	 * @return
	 */
	public Node<T> findMinNodeFromRight(Node<T> target) {
		//从当前节点的右子树中找出最小的节点元素
		Node<T> min = target.getRight();
		//如果存在左孩子，就一直往左
		while(min.getLeft() != null) {
			min = min.getLeft();
		}
		//不存在左孩子，则返回当前节点
		return min;
	}
}
